package everyday;

public class T1012 {
    String num;
    public int numDupDigitsAtMostN(int n) {
        num = String.valueOf(n);
        return n-numDupDigitsAtMostNHelp(0,0,true,false);
    }

    public int numDupDigitsAtMostNHelp(int i, int mask, boolean is_limit, boolean is_num) {
        if (i==num.length()){
            return is_num?1:0;
        }
        int sum = 0;
        int left = 0;
        int right = 9;
        int c = num.charAt(i) - '0';
        if (!is_num) {
            sum += numDupDigitsAtMostNHelp(i + 1, mask, false, false);
            left = 1;
        }
        if (is_limit) right = c;
        for (int j = left; j <= right; j++) {
            if ((mask >> j & 1) == 0) {
                sum += numDupDigitsAtMostNHelp(i + 1, mask | 1 << j, is_limit && c == j, true);
            }
        }
        return sum;
    }
}
